package A1_回溯;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LC_131分割回文串 {
    LinkedList<String> path=new LinkedList<>();
    List<List<String>> result=new ArrayList<>();
    public List<List<String>> partition(String s) {
        backtracking(s,0);
        return result;
    }
    public void backtracking(String s,int startIndex){
        if(startIndex>=s.length()){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i=startIndex;i<s.length();i++){
            String str=s.substring(startIndex,i+1);
            if(isPalindrome(str))
                path.add(str);
            else
                continue;
            backtracking(s,i+1);
            path.removeLast();

        }


    }
    //判断是否为回文字符串
//    public boolean isPalindrome(String str){
//        if(str==null||str.length()==0)
//            return false;
//        StringBuilder sb=new StringBuilder(str);
//        sb.reverse();
//        return str.equals(sb.toString());
//    }

    public boolean isPalindrome(String str){
        int left=0;
        int right=str.length()-1;
        while(left<right){
            if(str.charAt(left)!=str.charAt(right))
                return false;
            left++;
            right--;
        }
        return true;
    }
}
